import java.util.ArrayList;
import java.util.Comparator;
import java.util.Random;

public class Individual implements Comparable<Individual>{

	public Node root = null;
	double fitness = -1;

	int maxdepth;

	public Individual(int maxDep){
		maxdepth = maxDep;
	}

	public Individual deepCopy(){
		Individual other = new Individual(this.maxdepth);
		other.root = this.root.deepCopy();
		other.fitness = this.fitness;

		return other;
	}

	//THIS SELF-MODIFIES. Call it only on deep copies.
	public void crossOver(Individual other, Random rand){
		Object wrapper[];
		int coPoint = 1;

		if (this.root.size > 1) 
			coPoint = rand.nextInt(root.size-1)+1;

		wrapper = this.traverse(coPoint);
		Node thisPoint = (Node) wrapper[0];
		int thisCN = (Integer) wrapper[1];
		thisPoint = thisPoint.parent;

		coPoint = 1;	
		if (other.root.size > 1) 
			coPoint = rand.nextInt(other.root.size-1)+1;
		
		wrapper = other.traverse(coPoint);
		Node otherPoint = (Node) wrapper[0];
		int otherCN = (Integer) wrapper[1];
		
		otherPoint = otherPoint.parent;

		//actually swap
		Node temp = thisPoint.children.get(thisCN);
		thisPoint.children.set(thisCN, otherPoint.children.get(otherCN));
		
		if (thisPoint == thisPoint.children.get(thisCN)) {
			System.out.println("This point equals its parent");
		}
		
		thisPoint.children.get(thisCN).parent = thisPoint;

		otherPoint.children.set(otherCN, temp);
		
		if (otherPoint == otherPoint.children.get(otherCN)) {
			System.out.println("Other point equals its parent");
		}
		
		otherPoint.children.get(otherCN).parent = otherPoint;

		thisPoint.updateSize();
		otherPoint.updateSize();
	}

	protected Object[] traverse(int coPoint){
		boolean flag = false;
		Node here = root;
		int leftSum;
		int childNum=0;

		while(coPoint!=0 && !flag){
			if(here.order>0){
				if(coPoint!=0 && coPoint<=here.children.get(0).getSize()){
					here = here.children.get(0);
					coPoint-=1;
					childNum = 0;
				} else{
					leftSum = here.children.get(0).getSize()+1;
					if(coPoint<leftSum + here.children.get(1).getSize()){
						coPoint-=leftSum;
						here = here.children.get(1);
						childNum = 1;
					}else{
						coPoint-=leftSum;
						coPoint-=here.children.get(1).getSize();
						here = here.children.get(2);
						childNum = 2;
					}
				}
			}else if(here.order==0){
				assert(coPoint == 0);
				//you're there
				flag = true;
			}
		}
		Object[] returner = new Object[2];
		returner[0] = here;
		returner[1] = childNum;
		return returner;
	}

	//THIS SELF-MODIFIES. Call it only on deep copies.
	public void pointCrossOver(Individual other, Random rand){


		//traversal
		ArrayList<Node> goodNodes = new ArrayList<Node>();
		ArrayList<Node> goodNodesOther = new ArrayList<Node>();
		int childNumbers[] = new int[root.getSize()];
		Node current = root;
		Node otherCurrent = other.root;
		int index = 0;
		if(current.order == otherCurrent.order){
			goodNodes.add(current);
			goodNodesOther.add(otherCurrent);
		}
		//while loop
		while(index < goodNodes.size()){
			current = goodNodes.get(index);
			otherCurrent = goodNodesOther.get(index);
			for(int a=0;a<current.order;a++){
				if(current.children.get(a).order ==
						otherCurrent.children.get(a).order){

					goodNodes.add(current.children.get(a));
					goodNodesOther.add(otherCurrent.children.get(a));
					
					childNumbers[goodNodes.size() - 1] = a;
				}
			}

			index++;
		}
		
		if (goodNodes.size() <= 1)
			return;

		int coPoint = 1;

		if (goodNodes.size() > 0) 
			coPoint = rand.nextInt(goodNodes.size());
		
		if(coPoint>0){
			Node thisPoint = goodNodes.get(coPoint).parent;
			Node otherPoint = goodNodesOther.get(coPoint).parent;
			int cn = childNumbers[coPoint];

			Node temp = thisPoint.children.get(cn);
			thisPoint.children.set(cn, otherPoint.children.get(cn));
			thisPoint.children.get(cn).parent = thisPoint;

			otherPoint.children.set(cn, temp);
			otherPoint.children.get(cn).parent = otherPoint;

			thisPoint.updateSize();
			otherPoint.updateSize();
		}

	}

	public void pointMutation(Individual_Factory spawnPoint, Random rand){
		int target = rand.nextInt(root.getSize());
		
//		System.out.println("==");
//		System.out.println(target);
//		System.out.println(root.getSize());
		
		Object[] unpleasant = traverse(target);
		Node old = (Node)unpleasant[0];
		
		if (old.parent != null)
			old.parent.children.set((Integer)unpleasant[1],
					spawnPoint.getMatchingNode(old));
		else 
			root = spawnPoint.getMatchingNode(old);
	}

	public double evaluate(double[] varray){
		double ret = 0;

		try {
			ret = root.evaluate(varray);
		} catch (IndexOutOfBoundsException e) {
			System.out.println(this.toString());
			System.exit(1);
		}

		return ret;
	}

	public int compareTo(Individual arg0) {
		return ((Double)this.fitness).compareTo(arg0.fitness);
	}

	public String toString(){
		return ("Fitness: "+fitness/(Math.sqrt(Math.sqrt(root.getSize())))+"\nFunction: "+root.toString());
	}


}
